#include <bits/stdc++.h>

using namespace std;

// 三堆石头拿取斐波那契数博弈
// 有三堆石头，数量分别为a、b、c
// 两个人轮流拿，每次可以选择其中一堆石头，拿取斐波那契数的石头
// 拿到最后一颗石子的人获胜，根据a、b、c返回谁赢
// 来自真实大厂笔试，每堆石子的数量在10^5以内
// 没有在线测试，对数器验证

// 如果MAXN变大
// 相应的要修改f数组
const int MAXN = 201;
// MAXN以内的斐波那契数
int f[] = { 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 };
int len = sizeof(f) / sizeof(int);
string dp[MAXN][MAXN][MAXN];
// sg定理
int sg[MAXN];
bool appear[MAXN];

// 动态规划方法彻底尝试
// 为了验证
string win1(int a, int b, int c)
{
    // 假设当前的先手来行动
    // 注意不是全局的先手，是当前的先手来行动！
    // 当前！当前！当前！
    if(a + b + c == 0) 
    {
        // 当前的先手，面对这个局面
        // 返回当前的后手赢
        return "后手";
    }
    if(!dp[a][b][c].empty()) return dp[a][b][c];
    // ans : 赢的是当前的先手，还是当前的后手
    string ans = "后手";
    for(int i = 0; i < len; ++i)
    {
        if(f[i] <= a)
        {
            if(win1(a - f[i], b, c) == "后手")
            {
                // 后续过程的赢家是后续过程的后手
                // 那就表示当前的先手，通过这个后续过程，能赢
                ans = "先手";
                break;
            }
        }
        if(f[i] <= b)
        {
            if(win1(a, b - f[i], c) == "后手")
            {
                // 后续过程的赢家是后续过程的后手
                // 那就表示当前的先手，通过这个后续过程，能赢
                ans = "先手";
                break;
            }
        }
        if(f[i] <= c)
        {
            if(win1(a, b, c - f[i]) == "后手")
            {
                // 后续过程的赢家是后续过程的后手
                // 那就表示当前的先手，通过这个后续过程，能赢
                ans = "先手";
                break;
            }
        }
    }
    dp[a][b][c] = ans;
    return ans;
}

// O(10^5 * 24 * 2)
void build()
{
    for(int i = 1; i < MAXN; ++i)
    {
        memset(appear, 0, sizeof appear);
        for(int j = 0; j < len && i - f[j] >= 0; ++j)
        {
            appear[sg[i - f[j]]] = true;
        }
        for(int s = 0; s < MAXN; ++s)
        {
            if(!appear[s])
            {
                sg[i] = s;
                break;
            }
        }
    }
}

string win2(int a, int b, int c)
{
    return (sg[a] ^ sg[b] ^ sg[c]) != 0 ? "先手" : "后手";
}

int main() 
{
    build();
    cout << "测试开始" << endl;
    for(int a = 0; a < MAXN; a++) 
    {
        for(int b = 0; b < MAXN; b++) 
        {
            for(int c = 0; c < MAXN; c++) 
            {
                string ans1 = win1(a, b, c);
                string ans2 = win2(a, b, c);
                if (ans1 != ans2) cout << "出错了！" << endl;
            }
        }
    }
    cout << "测试结束" << endl;
    // 试图找到简洁规律，想通过O(1)的过程就得到sg(x)
    // 于是打印200以内的sg值，开始观察
    // 刚开始有规律，但是在sg(138)之后开始发生异常波动
    // 这道题在考的时候，数据量并没有大到需要O(1)的过程才能通过
    // 那就用build方法计算sg值，不再找寻简洁规律
    // 考试时一切根据题目数据量来决定是否继续优化
    for(int i = 0; i < MAXN; i++)
    {
        cout << "sg(" << i << ") : " << sg[i] << endl;
    }
        
    return 0;
}